package com.zhanghp.class027;

import java.util.PriorityQueue;

/**
 * 将数组和减半的最少操作次数
 * 测试链接 : https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/
 *
 * @author zhanghp
 * @since 2024-04-01 22:45
 */
public class Code03_MinimumOperationToHalveArraySum {

    static class Solution {
        public static int halveArray(int[] nums) {
            // 大根堆
            PriorityQueue<Double> queue = new PriorityQueue<>((a, b) -> b.compareTo(a));
            double sum = 0;
            for (int i = 0; i < nums.length; i++) {
                queue.offer((double) nums[i]);
                sum += nums[i];
            }

            sum /= 2;

            int ans = 0;

            for (double minus = 0, cur; minus < sum; ans++, minus += cur) {
                cur = queue.poll() / 2;
                queue.offer(cur);
            }

            return ans;
        }
    }

    static class Solution2 {

        public static void main(String[] args) {
            int[] in = {5,19,8,1};
            halveArray(in);
        }

        public static int MAXN = 100001;
        public static long[] heap = new long[MAXN];

        public static int size;

        public static int halveArray(int[] nums) {
            size = nums.length;
            long sum = 0;
            // 向下调整
            for (int i = size - 1; i >= 0; i--) {
                heap[i] = (long) nums[i] << 20;
                sum += heap[i];
                heapify(i);
            }
            sum /= 2;
            long cur;
            int ans = 0;
            for(long minus = 0; minus < sum ; minus += cur, ans ++){
                heap[0] =  heap[0] / 2;
                cur = heap[0];
                heapify(0);
            }
            return ans;
        }

        public static void heapify(int i) {
            int l = (i << 1) + 1;
            while (l < size) {
                int best = l + 1 < size && heap[l + 1] > heap[l] ? l + 1 : l;
                if (heap[best] <= heap[i]) {
                    break;
                }
                swap(i, best);
                i = best;
                l = (best << 1) + 1;
            }
        }

        public static void swap(int i, int j) {
            long tmp = heap[i];
            heap[i] = heap[j];
            heap[j] = tmp;
        }

        public static void swapEor(int a, int b){
            if (a == b || heap[a] == heap[b]) return;
            heap[a] = heap[a] ^ heap[b];
            heap[b] = heap[a] ^ heap[b];
            heap[a] = heap[b] ^ heap[a];
        }
    }
}
